// 动态规划
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/// @brief 爬楼梯问题，一共n个台阶，每次你可以爬1或2个台阶，求有多少种不同的方法可以爬到楼顶
/// @param n 楼梯数
/// @return 方法数
int climbStairs(int n)
{
	// 边界：n = 1或者2时
	// 刚好这两种情况与n是相等的
	if (n == 1 || n == 2)
	{
		return n;
	}
	// 因为每次是根据前面两个递推的，所以我们借助几个变量记录一下上一次的值，上上次的值以及本次结果即可
	// a和b初始时对应的是n = 1和n = 2的情况结果因为这里我们从3开始递推，当递推到第n次时，a和b则记录了第n - 2和第n - 1次结果
	int i, a = 1, b = 2, result;
	for (i = 3; i <= n; i++)
	{
		result = a + b;
		// 下一次就是第i + 1次了，因此a记录第i - 1次，b记录第i次也就是本次
		a = b;
		b = result;
	}
	return result;
}

/// @brief 求两个字符串的最长连续公共子串
/// @param str1 第一个字符串
/// @param str2 第二个字符串
/// @return 其最长公共子串
char *longestPublicString(char str1[], char str2[])
{
	// 使用动态规划的方式解决
	// 先建立一个二维数组dp记录用于记录公共最长字符串最大长度，行数为str1的长度，列数为str2的长度
	// 如果str1[i] == str2[j]且i == 0或j == 0，则赋值dp[i][j] = 1，若i和j有一个不为0则赋值dp[i][j] = dp[i - 1][j - 1] + 1，不相等直接赋值为0
	// 找到dp中最大的值dp[maxi][maxj]，那么最长子串即为str1下标的maxi - dp[maxi][maxj] + 1到maxi部分（或者str2下标的maxj - dp[maxi][maxj] + 1到maxj部分）
	int i, j, length1 = strlen(str1), length2 = strlen(str2), maxLength = 0, maxIndex;
	int dp[length1][length2];
	for (i = 0; i < length1; i++)
	{
		for (j = 0; j < length2; j++)
		{
			if (str1[i] == str2[j])
			{
				dp[i][j] = (i == 0 || j == 0) ? 1 : dp[i - 1][j - 1] + 1;
				// 与此同时记录最大长度
				if (dp[i][j] > maxLength)
				{
					maxLength = dp[i][j];
					maxIndex = i;
				}
			}
			else
			{
				dp[i][j] = 0;
			}
		}
	}
	// 返回最大字符串
	char *maxStr = (char *)calloc(maxLength + 1, sizeof(char));
	for (i = 0, j = maxIndex - maxLength + 1; i < maxLength; i++, j++)
	{
		maxStr[i] = str1[j];
	}
	maxStr[i] = '\0';
	return maxStr;
}

/// @brief 求两个字符串的最大非连续公共子序列长度，一个字符串的最大非连续子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串
/// @param str1 第一个字符串
/// @param str2 第二个字符串
/// @return 最长序列长度
int maxPublicDiscontinuity(char str1[], char str2[])
{
	int len1 = strlen(str1), len2 = strlen(str2), i, j;
	// 记录最长公共子序列的二维数组
	// dp[i][j]表示str1字符串的0 ~ i - 1部分和str2字符串的0 ~ j - 1部分的最长非连续公共子序列长度
	// 因此先得到特殊情况：dp[i][0]和dp[0][j]都是0（str1末尾后面没有和str2相等的，反过来同理）
	int dp[len1 + 1][len2 + 1];
	for (i = 0; i <= len1; i++)
	{
		dp[i][0] = 0;
	}
	for (j = 0; j <= len2; j++)
	{
		dp[0][j] = 0;
	}
	for (i = 1; i <= len1; i++)
	{
		for (j = 1; j <= len2; j++)
		{
			// 当比较两者相等时，则可以记录一次相等长度
			if (str1[i - 1] == str2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				// 否则，记录不同的字符之前的最长子序列
				dp[i][j] = dp[i][j - 1] > dp[i - 1][j] ? dp[i][j - 1] : dp[i - 1][j];
			}
		}
	}
	return dp[len1][len2];
}

/// @brief 最长上升子序列
/// @param nums 数组
/// @param numsSize 数组长度
/// @return 子序列长度
int lengthOfLIS(int nums[], int numsSize)
{
	if (numsSize == 0)
	{
		return 0;
	}
	// dp[i]表示nums[0...i]这个序列间的最长上升子序列
	int dp[numsSize], i, j, max = 1;
	dp[0] = 1;
	for (i = 1; i < numsSize; i++)
	{
		dp[i] = 1;
		// 找到nums[0...i - 1]中的最长的上升子序列
		for (j = 0; j < i; j++)
		{
			if (nums[i] > nums[j])
			{
				dp[i] = dp[i] > (dp[j] + 1) ? dp[i] : (dp[j] + 1);
			}
		}
		if (max < dp[i])
		{
			max = dp[i];
		}
	}
	return max;
}